package www.study.com;

import java.util.HashMap;
import java.util.Map;

public class code3 {
    public static void main(String[] args) {

    }
    class Solution {
        //方法二：滑动窗口
        public int lengthOfLongestSubstring(String s) {
            Map<Character,Integer> rempos = new HashMap<Character,Integer>();
            int res = 0;
            for(int i = 0 ,j = 0 ; i < s.length() ; i++){
                //i：窗口右边界   j：窗口左边界
                if(rempos.containsKey(s.charAt(i))){
                    //j更新位置，如果这个字符上次出现的位置在j的后方，则j后移，否则不动
                    j = Math.max(j,rempos.get(s.charAt(i)));
                }
                res = Math.max(res,i - j + 1);
                rempos.put(s.charAt(i),i + 1);
            }
            return res;
        }
        //方法一：动态规划
        // public int lengthOfLongestSubstring(String s) {
        //     if(s == null || s.length() == 0){
        //         return 0;
        //     }
        //     char[] chs = s.toCharArray();
        //     int[] dp = new int[chs.length];
        //     Map<Character,Integer> map = new HashMap<>();
        //     dp[0] = 1;
        //     map.put(chs[0],0);
        //     int res = 1;
        //     for(int i = 1 ; i < chs.length ; i++){
        //         if(!map.containsKey(chs[i])){
        //             dp[i] = dp[i - 1] + 1;
        //         }else{
        //             if(map.get(chs[i]) + dp[i - 1] >= i){
        //                 dp[i] = i - map.get(chs[i]);
        //             }else{
        //                 dp[i] = dp[i - 1] + 1;
        //             }
        //         }
        //         map.put(chs[i],i);
        //         res = Math.max(res,dp[i]);
        //     }
        //     return res;
        // }
    }
}
